package day_2022_9_to_12.Day;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/09/06 14:36
 **/
public class Day4_5_Offer59_MaxSlidingWindow {
    // 超时
    class Solution1 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] ans = new int[nums.length-k+1];
            int l = 0, r = k-1, p = 0, max;
            while(r < nums.length){
                ans[p] = getMax(nums, l, r);
                k++;
                l++;
                r++;
            }
            return ans;
        }
        private int getMax(int[] nums, int l, int r){
            int max = Integer.MIN_VALUE;
            for(int i = l; i <= r; ++i){
                max = Math.max(max, nums[i]);
            }
            return max;
        }
    }
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            Deque<Integer> q = new LinkedList<>();
            int[] ans = new int[nums.length-k+1];
            for(int i = 1-k, j = 0; j < nums.length; ++i, ++j){
                if(i > 0 && q.peekFirst() == nums[i-1]) q.removeFirst();
                while(!q.isEmpty() && q.peekLast() < nums[j]) q.removeLast();
                q.offer(nums[j]);
                if(i >= 0) ans[i] = q.peekFirst();
            }
            return ans;
        }
    }
}